Non-negative integers without consecutive ones

Time: O(1); Space: O(1); hard

Given a positive integer n, find the number of non-negative integers less than or equal to n,

whose binary representations do NOT contain consecutive ones.

Example 1:

Input: num = 5

Output: 5

Explanation:

  • Here are the non-negative integers <= 5 with their corresponding binary representations:

    0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101

  • Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Example 2:

Input：6

Output：5

Explanation

  • Here are the non-negative integers <= 6 with their corresponding binary representations:

    0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
6 : 110

  • Among them, integer 3 and 6 disobey the rule (two consecutive ones) and the other 5 satisfy the rule.

Constraints:

  • 1 <= n <= 10^9

[1]:

class Solution1(object):
    """
    Time: O(1)
    Space: O(1)
    """
    def findIntegers(self, num):
        """
        :type num: int
        :rtype: int
        """
        dp = [0] * 32
        dp[0], dp[1] = 1, 2

        for i in range(2, len(dp)):
            dp[i] = dp[i-1] + dp[i-2]
        result, prev_bit = 0, 0

        for i in reversed(range(31)):
            if (num & (1 << i)) != 0:
                result += dp[i]
                if prev_bit == 1:
                    result -= 1
                    break
                prev_bit = 1
            else:
                prev_bit = 0

        return result + 1

[2]:

s = Solution1()

num = 5
assert s.findIntegers(num) == 5

num = 6
assert s.findIntegers(num) == 5